Content Addressable Memory (CAM) devices are searchable memory devices that are used in applications that require high-speed searching. Such applications include packet forwarding and packet classification in Internet routers, data compression applications and neural networks.
CAMs are composed of conventional semiconductor memory (usually SRAM) with added comparison circuitry that enables a search operation to be completed in a single clock cycle.
A CAM device consists of an array of memory cells, each capable of storing one bit of information. The cells are each connected to respective feed lines which apply an input bit to compare with the bit stored in the cell, using the cell-dedicated comparison circuitry. If the input bit matches the stored bit, a match signal will be generated to the device output, providing the location of the match cell.
There are two types of CAM devices. The first is known as a Binary CAM device, in which the memory cells store one of a binary bit i.e. a 1 or a 0. The second type is known as a Ternary CAM or TCAM, in which the memory cells can store a 1, a 0 or a “don't care” (X) value, which will indicate a match with either a 1 or a 0 input to the device.
FIG. 1 shows an exemplary layout of a conventional TCAM 4 by 4 bit device 10. Device 10 has 16 memory cells 11, arranged in an array of four columns and four rows. An example of a TCAM cell is described in U.S. Pat. No. 5,313,590, the contents of which are hereby incorporated by reference.
Each cell 11 is electrically connected to a pair of feed lines or search lines 12a, 12a′ to 12d, 12d′. At an input to the device 10, search data (in this case a 4-bit word) is input to search line driver 14. Each pair of search lines 12a, 12a′ to 12d, 12d′ carries one bit of the four-bit word, to provide this bit to cells 11 in that column.
Each cell is also connected to one of match lines 13a to 13d, defining rows of cells 11. In this case, there are four rows of cells 11. If any one of the cells 11 connected to a match line 13a to 13d does not match the bit on its respective search line, the match line connected to that cell will indicate a no match. Only match lines for which all connected cells 11 match their respective search line bit will indicate a match.
In practice, this is accomplished by charging all match lines to an active or charged state at the beginning of each cycle. If a cell 11 does not match the bit on its search line, it will act to pull down its connected match line, thereby rendering it inactive, and indicating a no-match.
In the example of FIG. 1, at the beginning of a search cycle, all of the match lines 13a, 13b, 13c and 13d are charged to an active state. As the four-bit word 0110 is input to device 10, search lines 12a, 12a′ are charged to indicate a ‘0’, lines 12b, 12b′ are charged to indicate a “1”, lines 12c, 12c′ are charged to indicate a “1” and lines 12d, 12d′ are charged to indicate a “0”.
Looking now at the first column (between search lines 12a, 12a′), the top cell 11, storing a “1” does not match the data on its corresponding search lines, and so pulls match line 13a down to an inactive state, indicating a no-match. Match line will remain in the inactive, “no-match” state, regardless of whether any of the other cells match in that row.
Looking now at the second row, cell 16 storing a “0” matches with the data on search lines 12a, 12a′ and so does not pull down the active state of match line 13b. Looking at the other cells in that row, each cell stores data that matches the data on their corresponding search lines, and so no cells pull down match line 13b. Accordingly, match line 13b indicates a match.
Similarly, all cells in the third row (starting with cell 17) match their corresponding search lines and so match line 13c remains active to indicate a match.
In the fourth row, cell 18 stores a “1”, while search lines 12a, 12a′ store a “0”. Therefore, the mismatch pulls match line 13 down to an inactive state, indicating a mismatch. As previously described, match line 13d will remain inactive regardless of the state of the other cells in that row.
The output of the cell array, being no-match, match, match, no-match is fed into an encoder 19 via amplifiers 15a to 15d. Encoder 19 converts the match information from the match lines into addresses which are then used to locate the searched for data. This arrangement provides a highly parallel lookup engine, however, such an arrangement can suffer from sensitivity to noise and process variations, especially in the case of wider CAMs.
Accordingly, it is an object of the present invention to provide an improved CAM arrangement.